/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2024-05-06
 * Time: 17:27
 */
//115.不同的序列
public class Solution3 {
        public int numDistinct(String s, String t) {
            int n = s.length(), m = t.length();
            //1.创建dp
            //dp[i][j] t区间子串[0,j]有多少个在s区间子序列[0,i]
            int[][] dp = new int[m+1][n+1];
            //2.初始化
            s = " " + s;
            t = " " + t;
            for(int j = 0; j <= n; j++) {
                dp[0][j] = 1;
            }
            //3.状态转移
            for(int i = 1; i <= m; i++) {
                for(int j = 1; j <= n; j++) {
                    dp[i][j] = dp[i][j-1];
                    if(t.charAt(i) == s.charAt(j)) {
                        dp[i][j] += dp[i-1][j-1];
                    }
                }
            }
            //返回值
            return dp[m][n];
        }
}
